class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def canMerge(self, trees):
        """
        :type trees: List[TreeNode]
        :rtype: TreeNode
        """
        n = len(trees)
        d = {}
        p = [-1] * n
        self.count = 0
        q = {}
        for index, node in enumerate(trees):
            if node.val in d:
                return None
            else:
                d[node.val] = index
        for index, node in enumerate(trees):
            st = [node]
            while st:
                node = st.pop()
                if node.val in d and not node.left and not node.right and index != d[node.val]:
                    next_index = d[node.val]
                    if p[next_index] == -1:
                        p[next_index] = index
                        q[node] = trees[next_index]
                    else:
                        return None
                if node.left:
                    st.append(node.left)
                if node.right:
                    st.append(node.right)
        def dfs(base_node, last_min, last_max):
            if base_node in q:
                next_root = q[base_node]
                node = next_root
                while node:
                    min_val = node.val
                    node = node.left
                node = next_root
                while node:
                    max_val = node.val
                    node = node.right
                if min_val <= last_min or max_val >= last_max:
                    return False
                base_node.left = next_root.left
                base_node.right = next_root.right
                self.count += 1
            if base_node.left:
                next_min = last_min
                next_max = min(last_max, base_node.val)
                flag = dfs(base_node.left, next_min, next_max)
                if not flag:
                    return False
            if base_node.right:
                next_max = last_max
                next_min = max(last_min, base_node.val)
                flag = dfs(base_node.right, next_min, next_max)
                if not flag:
                    return False
            return True
        if p.count(-1) == 1:
            index = p.index(-1)
            root = trees[index]
            node = root
            if dfs(node, -float('inf'), float('inf')) and self.count == n - 1:
                return root
            else:
                return None
        else:
            return None

data = Solution()
trees = [TreeNode(2, TreeNode(1)), TreeNode(3, TreeNode(2), TreeNode(5)), TreeNode(5, TreeNode(4))]
print(data.canMerge(trees))
